package com.jinan.algorithm.HashTable;

import com.jinan.common.Pair;
import com.jinan.common.TreeNode;

import java.util.*;

public class HashTest {
    /**
     * 49. 字母异位词分组 <a href="https://leetcode.cn/problems/group-anagrams/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
     * 难度：中等
     * Tag: 哈希表 字符串
     * description:
     * 给定一个字符串数组 strs ，将 字母异位词 组合在一起。 可以按任意顺序返回结果列表。
     * 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
     * restrictions:
     * 1 <= strs.length <= 10^4
     * 0 <= strs[i].length <= 100
     * strs[i] 仅包含小写字母
     *
     * @param strs 字符串数组
     * @return 字母异位词 组合在一起的结果列表
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            int[] count = new int[26];
            for (char c : str.toCharArray()) {
                count[c - 'a']++;
            }
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 26; i++) {
                if (count[i] != 0) {
                    sb.append((char) ('a' + i));
                    sb.append(count[i]);
                }
            }
            List<String> list = map.getOrDefault(sb.toString(), new ArrayList<String>());
            list.add(str);
            map.put(sb.toString(), list);
        }
        return new ArrayList<>(map.values());
    }

    /**
     * 438. 找到字符串中所有字母异位词 <a href="https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
     * 难度：中等
     * Tag: 树 哈希表 双指针
     * description:
     * 给定两个字符串 s 和 p ，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
     * restrictions:
     * 1 <= s.length, p.length <= 3 * 10^4
     * s 和 p 仅由小写英文字母组成
     * @param s 字符串
     * @param p 字符串
     * @return 所有字母异位词的子串的起始索引
     */
    public List<Integer> findAnagrams(String s, String p) {
        int n = s.length();
        int m = p.length();
        ArrayList<Integer> ans = new ArrayList<>();
        if (n < m){
            return new ArrayList<>();
        }
        int[] count = new int[26];
        for (int i = 0; i < m; i++){
            count[p.charAt(i) - 'a']++;
        }
        int left = 0;
        int right = 0;
        for (; right < n; right++){
            count[s.charAt(right) - 'a']--;
            while(count[s.charAt(right) - 'a'] < 0){
                count[s.charAt(left) - 'a']++;
                left++;
            }
            if (right - left + 1 == m){
                ans.add(left);
            }
        }
        return ans;
    }

    /**
     * 128. 最长连续序列 <a href="https://leetcode.cn/problems/longest-consecutive-sequence/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
     * 难度：困难
     * Tag: 并查集 数组 哈希表
     * description:
     * 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
     * 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
     * restrictions:
     * 0 <= nums.length <= 10^5
     * -10^9 <= nums[i] <= 10^9
     *
     * @param nums 未排序的整数数组
     * @return 数字连续的最长序列的长度
     */
    public int longestConsecutive(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        int ans = 0;
        for (int num : nums) {
            set.add(num);
        }
        for (int num : nums) {
            if (!set.contains(num - 1)) {
                int start = num;
                while (set.contains(start + 1)) {
                    start++;
                }
                ans = Math.max(ans, start - num + 1);
            }
        }
        return ans;
    }

    /**
     * 3159. 查询数字在数组中出现的次数 <a href="https://leetcode.cn/problems/find-occurrences-of-an-element-in-an-array/description/">...</a>
     * 难度：中等
     * Tag: 数组 哈希表
     * description:
     * 给你一个整数数组 nums 和一个整数数组 queries 。
     * 找出 queries 中每个查询的答案：查询中第 k 个出现的 x 的下标是 nums 中第 k 个。如果 x 在 nums 中出现次数少于 k ，那么答案是 -1 。
     * restrictions:
     * 1 <= nums.length, queries.length <= 10^5
     * 1 <= nums[i], queries[i] <= 10^6
     *
     * @param nums    整数数组
     * @param queries 查询数组
     * @param x       查询中第 k 个出现的 x 的下标是 nums 中第 k 个
     * @return 查询的答案
     */
    public int[] occurrencesOfElement(int[] nums, int[] queries, int x) {
        //用哈希表记录所有等于 x 的 nums[i] 的下标 i。
//        HashMap<Integer, Integer> map = new HashMap<>();
//        int count = 0;
//        for (int i = 0; i < nums.length; i++){
//            if (nums[i] == x){
//                count++;
//                map.put(count, i);
//            }
//        }
//        int[] ans = new int[queries.length];
//        for (int i = 0; i < queries.length; i++){
//            ans[i] = map.getOrDefault(queries[i], -1);
//        }
//        return ans;

        //用 pos 数组记录所有等于 x 的 nums[i] 的下标 i。
        //对于每个询问 q=queries[i]，如果 q 大于 pos 的长度，则答案为 −1，否则答案为 pos[q−1]。
        ArrayList<Integer> pos = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == x) {
                pos.add(i);
            }
        }
        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            ans[i] = pos.size() < queries[i] ? -1 : pos.get(queries[i] - 1);
        }
        return ans;
    }

    /**
     * 1366. 通过投票对团队排名 <a href="https://leetcode.cn/problems/rank-teams-by-votes/description/">...</a>
     * 难度：中等
     * Tag: 投票 哈希表
     * description:
     * 现在有一个特殊的排名系统，依据参赛团队在投票人心中的次序进行排名，每个投票者都需要按从高到低的顺序对参与排名的所有团队进行排位。
     * 排名规则如下：
     * 参赛团队的排名次序依照其所获「排位第一」的票的多少决定。如果存在多个团队并列的情况，将继续考虑其「排位第二」的票的数量。以此类推，直到不再存在并列的情况。
     * 如果在考虑完所有投票情况后仍然出现并列现象，则根据团队字母的字母顺序进行排名。
     * 给你一个字符串数组 votes 代表全体投票者给出的排位情况，请你根据上述排名规则对所有参赛团队进行排名。
     * 请你返回能表示按排名系统 排序后 的所有团队排名的字符串。
     * restrictions:
     * 1 <= votes.length <= 1000
     * 1 <= votes[i].length <= 26
     * votes[i].length == votes[j].length for 0<=i,j<votes.length.
     * votes[i][j] 是一个字母，表示第 i 个投票者给出第 j 个团队的排名。
     * 所有字符都是大写英文字母。
     *
     * @param votes 字符串数组
     * @return 排好序的字符串
     */
    public String rankTeams(String[] votes) {
        int m = votes[0].length();
        int[][] count = new int[26][m + 1];
        for (String vote : votes) {
            for (int i = 0; i < m; i++) {
                count[vote.charAt(i) - 'A'][i]++;
            }
        }
        Character[] chars = new Character[m];
        for (int i = 0; i < m; i++) {
            chars[i] = votes[0].charAt(i);
        }
        Arrays.sort(chars, (o1, o2) -> {
            for (int i = 0; i < m; i++) {
                if (count[o1 - 'A'][i] != count[o2 - 'A'][i]) {
                    return count[o2 - 'A'][i] - count[o1 - 'A'][i];
                }
            }
            return o1 - o2;
        });
        StringBuilder sb = new StringBuilder();
        for (Character c : chars) {
            sb.append(c);
        }
        return sb.toString();
    }

    /**
     * 41. 缺失的第一个正数 <a href="https://leetcode.cn/problems/first-missing-positive/description/">...</a>
     * 难度：困难
     * Tag: 数组 哈希表
     * description: 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
     * restrictions:
     * 1 <= nums.length <= 5 * 10^5
     * -2^31 <= nums[i] <= 2^31 - 1
     *
     * @param nums 未排序的整数数组
     * @return int 未出现的最小正整数
     */
    public int firstMissingPositive(int[] nums) {
        //方法1：数组记录数字出现的次数
        int n = nums.length;
        int[] a = new int[n + 1];
        for (int num : nums) {
            if (num > 0 && num <= n) {
                a[num] = 1;
            }
        }
        for (int i = 1; i <= n; i++) {
            if (a[i] == 0) {
                return i;
            }
        }
        return n + 1;
    }

    public int firstMissingPositive2(int[] nums) {
        //方法2：将数组中的数字放到正确的位置上，也就是将nums数组看作一个特殊的哈希表，哈希函数就是nums[i] = i+1.
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }

    /**
     * 442. 数组中重复的数据 <a href="https://leetcode.cn/problems/find-all-duplicates-in-an-array/description/">...</a>
     * 难度：中等
     * Tag: 数组 哈希表
     * description: 给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内，
     * 且每个整数出现 最多两次 。请你找出所有出现 两次 的整数，并以数组形式返回。
     * restrictions:
     * n == nums.length
     * 1 <= n <= 10^5
     * 1 <= nums[i] <= n
     * nums 中的每个元素出现 一次 或 两次
     *
     * @param nums 整数数组
     * @return List<Integer> 出现两次的整数
     */
    public List<Integer> findDuplicates(int[] nums) {
        ArrayList<Integer> ans = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] != nums[nums[i] - 1]) {
                int temp = nums[i];
                nums[i] = nums[temp - 1];
                nums[temp - 1] = temp;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i + 1) {
                ans.add(nums[i]);
            }
        }
        return ans;
    }

    /**
     * 73. 矩阵置零 <a href="https://leetcode.cn/problems/set-matrix-zeroes/description/">...</a>
     * 难度：中等
     * Tag: 数组 哈希表
     * description: 给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
     * restrictions:
     * m == matrix.length
     * n == matrix[0].length
     * 1 <= m, n <= 200
     * -2^31 <= matrix[i][j] <= 2^31 - 1
     *
     * @param matrix 矩阵
     */
    public void setZeroes(int[][] matrix) {
        //方法1：使用第一行和第一列记录后面的行和列是否要置零
        //使用两个标志位记录第一行和第一列是否要置零
        boolean row0 = false, col0 = false;
        int m = matrix.length;
        int n = matrix[0].length;
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                col0 = true;
                break;
            }
        }
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                row0 = true;
                break;
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (col0) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
        if (row0) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }
    }

    /**
     * 3280. 日期到二进制的转换 <a href="https://leetcode.cn/problems/convert-date-to-binary/description/">...</a>
     * 难度：简单
     * Tag: 数学 数组
     * description: 给你一个字符串 date，它的格式为 yyyy-mm-dd，表示一个公历日期。
     * date 可以重写为二进制表示，只需要将年、月、日分别转换为对应的二进制表示（不带前导零）并遵循 year-month-day 的格式。
     * 返回 date 的 二进制 表示。
     * restrictions:
     * 1 <= date.length <= 10
     * date[4] == date[7] == '-'，其余的 date[i] 都是数字。
     * 输入保证 date 代表一个有效的公历日期，日期范围从 1900 年 1 月 1 日到 2100 年 12 月 31 日（包括这两天）。
     * @param date 日期
     * @return String 二进制表示
     */
    public String convertDateToBinary(String date) {
        String[] a= date.split("-");
        for (int i = 0; i < 3; i++){
            a[i]=Integer.toBinaryString(Integer.parseInt(a[i]));
        }
        return String.join("-", a);
    }

    /**
     * 54. 螺旋矩阵 <a href="https://leetcode.cn/problems/spiral-matrix/description/">...</a>
     * 难度：中等
     * Tag: 数组 矩阵
     * description: 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
     * restrictions:
     * m == matrix.length
     * n == matrix[i].length
     * 1 <= m, n <= 10
     * -100 <= matrix[i][j] <= 100
     * @param matrix 矩阵
     * @return List<Integer> 顺时针螺旋顺序
     */
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList<>();
        int m = matrix.length;
        int n = matrix[0].length;
        int left = 0, right = n - 1, top = 0, bottom = m - 1;
        while (left <= right && top <= bottom) {
            for (int i = left; i <= right; i++) {
                ans.add(matrix[top][i]);
            }
            for (int i = top + 1; i <= bottom; i++) {
                ans.add(matrix[i][right]);
            }
            if (left < right && top < bottom) {
                for (int i = right - 1; i > left; i--) {
                    ans.add(matrix[bottom][i]);
                }
                for (int i = bottom; i > top; i--) {
                    ans.add(matrix[i][left]);
                }
            }
            left++;
            right--;
            top++;
            bottom--;
        }
        return ans;
    }
    /**
     * 1123. 最深叶节点的最近公共祖先 <a href="https://leetcode.cn/problems/lowest-common-ancestor-of-deepest-leaves/description/">...</a>
     * 难度：困难
     * Tag: 树 深度优先搜索 广度优先搜索 二叉树
     * description: 给你一个二叉树，请你返回其 最深 的叶节点的最近公共祖先。
     * restrictions:
     * 树中节点数目在范围 [1, 1000] 内。
     * 1 <= Node.val <= 1000
     * 树中每个节点的 val 互不相同。
     * 回想一下：
     * 叶节点 是指没有子节点的节点。
     * 最深叶节点 是指距离根节点最远的叶节点。
     * @param root 二叉树
     * @return 最近公共祖先
     */
    public TreeNode<Integer> lcaDeepestLeaves(TreeNode<Integer> root) {
        return lcaDeepestLeavesdfs(root).getValue();
    }
    public Pair<Integer, TreeNode<Integer>> lcaDeepestLeavesdfs(TreeNode<Integer> node) {
        if(node == null){
            return new Pair<>(0, null);
        }
        Pair<Integer, TreeNode<Integer>> left = lcaDeepestLeavesdfs(node.left);
        Pair<Integer, TreeNode<Integer>> right = lcaDeepestLeavesdfs(node.right);
        if(left.getKey().equals(right.getKey())){
            return new Pair<>(left.getKey() + 1, node);
        }else if(left.getKey() > right.getKey()){
            return new Pair<>(left.getKey() + 1, left.getValue());
        }else{
            return new Pair<>(right.getKey() + 1, right.getValue());
        }
    }

    /**
     * 347. 前 K 个高频元素 <a href="https://leetcode.cn/problems/top-k-frequent-elements/description/">...</a>
     * 难度：中等
     * Tag: 数组 哈希表 分治 堆（优先队列） 快速选择 桶排序 计数 排序
     * description: 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
     * restrictions:
     * 1 <= nums.length <= 10^5
     * k 的取值范围是 [1, nums.length]
     * 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
     */
    public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            pq.offer(entry);
        }
        int[] res = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            res[i] = pq.poll().getKey();
        }
        return res;
    }
    public int[] topKFrequent2(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        int max = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()){
            if(entry.getValue() > max){
                max = entry.getValue();
            }
        }
        List<Integer>[] bucket = new List[max + 1];
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int freq = entry.getValue();
            if (bucket[freq] == null) {
                bucket[freq] = new ArrayList<>();
            }
            bucket[freq].add(entry.getKey());
        }
        int[] res = new int[k];
        for (int i = max; i >= 0 && k > 0; i--){
            if (bucket[i] != null) {
                for (int num : bucket[i]) {
                    res[--k] = num;
                }
            }
        }
        return res;
    }
}

